package leetcode.editor.vscdev.backtracking;

import java.util.ArrayList;
import java.util.List;

/* 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，
返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。
你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。 */
public class lc93 {
    class Solution {
        private List<String> result = new ArrayList<>();
        public List<String> restoreIpAddresses(String s) {
            if (s.length() > 12) return result; // 算是剪枝了
            backtracking(new StringBuilder(s), 0, 0);
            return result;
        }
        public void backtracking(StringBuilder s, int index, int pointCount){
            if (pointCount == 3) {
                if (isValid(s, index, s.length() - 1)) {
                    result.add(s.toString());
                }
                return;
            }
            for (int i = index; i < s.length() && i < index + 3; i++) {
                if (isValid(s, index, i)) {
                    s.insert(i + 1, '.');
                    backtracking(s, i + 2, pointCount + 1);
                    s.deleteCharAt(i + 1); // 回溯删掉逗点
                } else {
                    break;
                }
            }
        }
        private boolean isValid(StringBuilder s,int start,int end){
            if (start > end) {
                return false;
            }
            String temp = s.substring(start, end + 1);
            if (temp.length() > 3 || temp.length() == 0 || (temp.charAt(0) == '0' && temp.length() > 1) || Integer.parseInt(temp) > 255) {
                return false;
            }
            return true;
        }
    }
}
